package BinaryTree;
/*
* 打家劫舍3
* TODO 动态规划再做
*
* 不偷： 选取左右结点偷与不偷的最大值
* */
public class Rob337 {
    public int rob(TreeNode root) {
        int[]  res=dfs(root);
        return Math.max(res[0],res[1]);
    }

    private int[] dfs(TreeNode root) {
        if(root==null){
            return new int[]{0,0};
        }
        int[] left=dfs(root.left);
        int[] right=dfs(root.right);

        int[] tmp=new int[2];
        //不偷
        tmp[0]=Math.max(left[0],left[1])+Math.max(right[0],right[1]);
        //偷
        tmp[1]=left[0]+right[0]+root.val;
        return tmp;
    }
}
